/*
 * Copyright 2010-2012 Susanta Tewari. <freecode4susant@users.sourceforge.net>
 *
 * This program is a derivative work from the original sources at
 * Apache Commons (http://commons.apache.org/).
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package org.apache.commons.lang;

import org.apache.commons.lang.builder.ToStringBuilder;
import org.apache.commons.lang.builder.ToStringStyle;

import java.lang.reflect.Array;

/**
 * <p>Operations on arrays, primitive arrays (like <code>int[]</code>) and
 * primitive wrapper arrays (like <code>Integer[]</code>).</p>
 * <p>This class tries to handle <code>null</code> input gracefully.
 * An exception will not be thrown for a <code>null</code>
 * array input. However, an Object array that contains a <code>null</code>
 * element may throw an exception. Each method documents its behaviour.</p>
 *
 * @author Stephen Colebourne
 * @author Moritz Petersen
 * @author <a href="mailto:fredrik@westermarck.com">Fredrik Westermarck</a>
 * @author Nikolay Metchev
 * @author Matthew Hawthorne
 * @author Tim O'Brien
 * @author Pete Gieser
 * @author Gary Gregory
 * @author <a href="mailto:equinus100@hotmail.com">Ashwin S</a>
 * @author Maarten Coene
 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
 * @since 2.0
 */
public class ArrayUtils {

    /**
     * The index value when an element is not found in a list or array: <code>-1</code>.
     * This value is returned by methods in this class and can also be used in comparisons with values returned by
     * various method from {@link java.util.List}.
     */
    public static final int INDEX_NOT_FOUND = -1;

    /**
     * An empty immutable {@code Integer} array.
     */
    public static final Integer[] EMPTY_INTEGER_OBJECT_ARRAY = new Integer[0];

    /**
     * An empty immutable {@code Byte} array.
     */
    public static final Byte[] EMPTY_BYTE_OBJECT_ARRAY = new Byte[0];

    /**
     * An empty immutable {@code Class} array.
     */
    static final Class<?>[] EMPTY_CLASS_ARRAY = new Class[0];

    /**
     * An empty immutable {@code Double} array.
     */
    public static final Double[] EMPTY_DOUBLE_OBJECT_ARRAY = new Double[0];

    /**
     * An empty immutable {@code int} array.
     */
    public static final int[] EMPTY_INT_ARRAY = new int[0];

    /**
     * An empty immutable {@code byte} array.
     */
    public static final byte[] EMPTY_BYTE_ARRAY = new byte[0];

    /**
     * An empty immutable {@code double} array.
     */
    public static final double[] EMPTY_DOUBLE_ARRAY = new double[0];

    /**
     * An empty immutable {@code char} array.
     */
    public static final char[] EMPTY_CHAR_ARRAY = new char[0];

    /**
     * Constructs ...
     *
     */
    private ArrayUtils() {}

    /**
     * <p>Copies the given array and adds the given element at the end of the new array.</p>
     * <p>The new array contains the same elements of the input
     * array plus the given element in the last position. The component type of
     * the new array is the same as that of the input array.</p>
     * <p>If the input array is {@code null}, a new one element array is returned
     * whose component type is the same as the element, unless the element itself is null,
     * in which case the return type is Object[]</p>
     * <pre>
     * ArrayUtils.add(null, null)      = [null]
     * ArrayUtils.add(null, "a")       = ["a"]
     * ArrayUtils.add(["a"], null)     = ["a", null]
     * ArrayUtils.add(["a"], "b")      = ["a", "b"]
     * ArrayUtils.add(["a", "b"], "c") = ["a", "b", "c"]
     * </pre>
     *
     * @param <T> the component type of the array
     * @param array the array to "add" the element to, may be {@code null}
     * @param element the object to add, may be {@code null}
     * @return A new array containing the existing elements plus the new element
     *         The returned array type will be that of the input array (unless null),
     *         in which case it will have the same type as the element.
     *         If both are null, an IllegalArgumentException is thrown
     * @since 2.1
     */
    public static <T> T[] add(T[] array, T element) {

        Class<?> type;

        if (array != null) {
            type = array.getClass();
        } else if (element != null) {
            type = element.getClass();
        } else {
            throw new IllegalArgumentException("Arguments cannot both be null");
        }

        @SuppressWarnings("unchecked")    // type must be T
            T[] newArray = (T[]) copyArrayGrow1(array, type);

        newArray[newArray.length - 1] = element;

        return newArray;
    }


    /**
     * Returns a copy of the given array of size 1 greater than the argument.
     * The last value of the array is left to the default value.
     *
     * @param array The array to copy, must not be {@code null}.
     * @param newArrayComponentType If {@code array} is {@code null}, create a
     * size 1 array of this type.
     * @return A new copy of the array of size 1 greater than the input.
     */
    private static Object copyArrayGrow1(Object array, Class<?> newArrayComponentType) {

        if (array != null) {

            int    arrayLength = Array.getLength(array);
            Object newArray    = Array.newInstance(array.getClass().getComponentType(),
                                     arrayLength + 1);

            System.arraycopy(array, 0, newArray, 0, arrayLength);

            return newArray;
        }

        return Array.newInstance(newArrayComponentType, 1);
    }


    /**
     * <p>Adds all the elements of the given arrays into a new array.</p>
     * <p>The new array contains all of the element of {@code array1} followed
     * by all of the elements {@code array2}. When an array is returned, it is always
     * a new array.</p>
     * <pre>
     * ArrayUtils.addAll(null, null)     = null
     * ArrayUtils.addAll(array1, null)   = cloned copy of array1
     * ArrayUtils.addAll(null, array2)   = cloned copy of array2
     * ArrayUtils.addAll([], [])         = []
     * ArrayUtils.addAll([null], [null]) = [null, null]
     * ArrayUtils.addAll(["a", "b", "c"], ["1", "2", "3"]) = ["a", "b", "c", "1", "2", "3"]
     * </pre>
     *
     * @param <T> the component type of the array
     * @param array1 the first array whose elements are added to the new array, may be {@code null}
     * @param array2 the second array whose elements are added to the new array, may be {@code null}
     * @return The new array, {@code null} if both arrays are {@code null}.
     *         The type of the new array is the type of the first array,
     *         unless the first array is null, in which case the type is the same as the second array.
     * @since 2.1
     */
    public static <T> T[] addAll(T[] array1, T... array2) {

        if (array1 == null) {
            return clone(array2);
        } else if (array2 == null) {
            return clone(array1);
        }

        final Class<?> type1       = array1.getClass().getComponentType();
        @SuppressWarnings("unchecked")    // OK, because array is of type T
            T[]           joinedArray = (T[]) Array.newInstance(type1,
                                            array1.length + array2.length);

        System.arraycopy(array1, 0, joinedArray, 0, array1.length);

        try {
            System.arraycopy(array2, 0, joinedArray, array1.length, array2.length);
        } catch (ArrayStoreException ase) {

            // Check if problem was due to incompatible types

            /*
             * We do this here, rather than before the copy because:
             * - it would be a wasted check most of the time
             * - safer, in case check turns out to be too strict
             */
            final Class<?> type2 = array2.getClass().getComponentType();

            if (!type1.isAssignableFrom(type2)) {

                throw new IllegalArgumentException("Cannot store " + type2.getName()
                                                   + " in an array of " + type1.getName(), ase);
            }

            throw ase;    // No, so rethrow original
        }

        return joinedArray;
    }


    /**
     * <p>Shallow clones an array returning a typecast result and handling
     * {@code null}.</p>
     * <p>The objects in the array are not cloned, thus there is no special
     * handling for multi-dimensional arrays.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param <T> the component type of the array
     * @param array the array to shallow clone, may be {@code null}
     * @return the cloned array, {@code null} if {@code null} input
     */
    static <T> T[] clone(T[] array) {

        if (array == null) {
            return null;
        }

        return array.clone();
    }


    /**
     * <p>Checks if the value is in the given array.</p>
     * <p>The method returns <code>false</code> if a <code>null</code> array is passed in.</p>
     *
     * @param array the array to search through
     * @param valueToFind the value to find
     * @return <code>true</code> if the array contains the object
     */
    public static boolean contains(int[] array, int valueToFind) {

        return indexOf(array, valueToFind) != INDEX_NOT_FOUND;
    }


    // int IndexOf

    /**
     * <p>Finds the index of the given value in the array.</p>
     * <p>This method returns {@link #INDEX_NOT_FOUND} (<code>-1</code>) for a <code>null</code> input array.</p>
     *
     * @param array the array to search through for the object, may be <code>null</code>
     * @param valueToFind the value to find
     * @return the index of the value within the array,
     *         {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> array input
     */
    public static int indexOf(int[] array, int valueToFind) {

        return indexOf(array, valueToFind, 0);
    }


    /**
     * <p>Checks if an array of Objects is not empty or not {@code null}.</p>
     *
     * @param <T> the component type of the array
     * @param array the array to test
     * @return {@code true} if the array is not empty or not {@code null}
     * @since 2.5
     */
    static <T> boolean isNotEmpty(T[] array) {

        return ((array != null) && (array.length != 0));
    }


    /**
     * <p>Finds the index of the given value in the array starting at the given index.</p>
     * <p>This method returns {@link #INDEX_NOT_FOUND} (<code>-1</code>) for a <code>null</code> input array.</p>
     * <p>A negative startIndex is treated as zero. A startIndex larger than the array
     * length will return {@link #INDEX_NOT_FOUND} (<code>-1</code>).</p>
     *
     * @param array the array to search through for the object, may be <code>null</code>
     * @param valueToFind the value to find
     * @param startIndex the index to start searching at
     * @return the index of the value within the array,
     *         {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> array input
     */
    static int indexOf(int[] array, int valueToFind, int startIndex) {

        if (array == null) {
            return INDEX_NOT_FOUND;
        }

        if (startIndex < 0) {
            startIndex = 0;
        }

        for (int i = startIndex; i < array.length; i++) {

            if (valueToFind == array[i]) {
                return i;
            }
        }

        return INDEX_NOT_FOUND;
    }


    // Object IndexOf
    // -----------------------------------------------------------------------

    /**
     * <p>Finds the index of the given object in the array.</p>
     * <p>This method returns {@link #INDEX_NOT_FOUND} ({@code -1}) for a {@code null} input array.</p>
     *
     * @param array the array to search through for the object, may be {@code null}
     * @param objectToFind the object to find, may be {@code null}
     * @return the index of the object within the array,
     *         {@link #INDEX_NOT_FOUND} ({@code -1}) if not found or {@code null} array input
     */
    public static int indexOf(Object[] array, Object objectToFind) {

        return indexOf(array, objectToFind, 0);
    }


    /**
     * <p>Checks whether two arrays are the same length, treating
     * {@code null} arrays as length {@code 0}.
     * <p>Any multi-dimensional aspects of the arrays are ignored.</p>
     *
     * @param array1 the first array, may be {@code null}
     * @param array2 the second array, may be {@code null}
     * @return {@code true} if length of arrays matches, treating
     *         {@code null} as an empty array
     */
    static boolean isSameLength(Object[] array1, Object[] array2) {

        if (((array1 == null) && (array2 != null) && (array2.length > 0))
                || ((array2 == null) && (array1 != null) && (array1.length > 0))
                || ((array1 != null) && (array2 != null) && (array1.length != array2.length))) {
            return false;
        }

        return true;
    }


    /**
     * <p>Finds the index of the given object in the array starting at the given index.</p>
     * <p>This method returns {@link #INDEX_NOT_FOUND} ({@code -1}) for a {@code null} input array.</p>
     * <p>A negative startIndex is treated as zero. A startIndex larger than the array
     * length will return {@link #INDEX_NOT_FOUND} ({@code -1}).</p>
     *
     * @param array the array to search through for the object, may be {@code null}
     * @param objectToFind the object to find, may be {@code null}
     * @param startIndex the index to start searching at
     * @return the index of the object within the array starting at the index,
     *         {@link #INDEX_NOT_FOUND} ({@code -1}) if not found or {@code null} array input
     */
    static int indexOf(Object[] array, Object objectToFind, int startIndex) {

        if (array == null) {
            return INDEX_NOT_FOUND;
        }

        if (startIndex < 0) {
            startIndex = 0;
        }

        if (objectToFind == null) {

            for (int i = startIndex; i < array.length; i++) {

                if (array[i] == null) {
                    return i;
                }
            }

        } else if (array.getClass().getComponentType().isInstance(objectToFind)) {

            for (int i = startIndex; i < array.length; i++) {

                if (objectToFind.equals(array[i])) {
                    return i;
                }
            }
        }

        return INDEX_NOT_FOUND;
    }


    /**
     * <p>Converts an array of primitive ints to objects.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param array an {@code int} array
     * @return an {@code Integer} array, {@code null} if null array input
     */
    public static Integer[] toObject(int[] array) {

        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_INTEGER_OBJECT_ARRAY;
        }

        final Integer[] result = new Integer[array.length];

        for (int i = 0; i < array.length; i++) {

            result[i] = Integer.valueOf(array[i]);
        }

        return result;
    }


    /**
     * <p>Converts an array of primitive bytes to objects.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param array a {@code byte} array
     * @return a {@code Byte} array, {@code null} if null array input
     */
    public static Byte[] toObject(byte[] array) {

        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_BYTE_OBJECT_ARRAY;
        }

        final Byte[] result = new Byte[array.length];

        for (int i = 0; i < array.length; i++) {

            result[i] = Byte.valueOf(array[i]);
        }

        return result;
    }


    /**
     * <p>Converts an array of primitive doubles to objects.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param array a {@code double} array
     * @return a {@code Double} array, {@code null} if null array input
     */
    public static Double[] toObject(double[] array) {

        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_DOUBLE_OBJECT_ARRAY;
        }

        final Double[] result = new Double[array.length];

        for (int i = 0; i < array.length; i++) {

            result[i] = Double.valueOf(array[i]);
        }

        return result;
    }


    // Int array converters
    // ----------------------------------------------------------------------

    /**
     * <p>Converts an array of object Integers to primitives.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param array a {@code Integer} array, may be {@code null}
     * @return an {@code int} array, {@code null} if null array input
     */
    public static int[] toPrimitive(Integer[] array) {

        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_INT_ARRAY;
        }

        final int[] result = new int[array.length];

        for (int i = 0; i < array.length; i++) {

            result[i] = array[i].intValue();
        }

        return result;
    }


    /**
     * <p>Outputs an array as a String, treating {@code null} as an empty array.</p>
     * <p>Multi-dimensional arrays are handled correctly, including
     * multi-dimensional primitive arrays.</p>
     * <p>The format is that of Java source code, for example <code>{a,b}</code>.</p>
     *
     * @param array the array to get a toString for, may be {@code null}
     * @return a String representation of the array, '{}' if null array input
     */
    static String toString(Object array) {

        return toString(array, "{}");
    }


    /**
     * <p>Outputs an array as a String handling {@code null}s.</p>
     * <p>Multi-dimensional arrays are handled correctly, including
     * multi-dimensional primitive arrays.</p>
     * <p>The format is that of Java source code, for example <code>{a,b}</code>.</p>
     *
     * @param array the array to get a toString for, may be {@code null}
     * @param stringIfNull the String to return if the array is {@code null}
     * @return a String representation of the array
     */
    static String toString(Object array, String stringIfNull) {

        if (array == null) {
            return stringIfNull;
        }

        return new ToStringBuilder(array, ToStringStyle.SIMPLE_STYLE).append(array).toString();
    }


    /**
     * <p>Converts an array of object Bytes to primitives.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param array a {@code Byte} array, may be {@code null}
     * @return a {@code byte} array, {@code null} if null array input
     */
    @SuppressWarnings("ReturnOfCollectionOrArrayField")
    public static byte[] toPrimitive(Byte[] array) {

        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_BYTE_ARRAY;
        }

        final byte[] result = new byte[array.length];

        for (int i = 0; i < array.length; i++) {

            result[i] = array[i].byteValue();
        }

        return result;
    }


    /**
     * <p>Converts an array of object Doubles to primitives.</p>
     * <p>This method returns {@code null} for a {@code null} input array.</p>
     *
     * @param array a {@code Double} array, may be {@code null}
     * @return a {@code double} array, {@code null} if null array input
     */
    @SuppressWarnings("ReturnOfCollectionOrArrayField")
    public static double[] toPrimitive(Double[] array) {

        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_DOUBLE_ARRAY;
        }

        final double[] result = new double[array.length];

        for (int i = 0; i < array.length; i++) {

            result[i] = array[i].doubleValue();
        }

        return result;
    }


    /**
     * <p>Removes the element at the specified position from the specified array.
     * All subsequent elements are shifted to the left (subtracts one from
     * their indices).</p>
     * <p>This method returns a new array with the same elements of the input
     * array except the element on the specified position. The component
     * type of the returned array is always the same as that of the input
     * array.</p>
     * <p>If the input array is {@code null}, an IndexOutOfBoundsException
     * will be thrown, because in that case no valid index can be specified.</p>
     * <pre>
     * ArrayUtils.remove(['a'], 0)           = []
     * ArrayUtils.remove(['a', 'b'], 0)      = ['b']
     * ArrayUtils.remove(['a', 'b'], 1)      = ['a']
     * ArrayUtils.remove(['a', 'b', 'c'], 1) = ['a', 'c']
     * </pre>
     *
     * @param array the array to remove the element from, may not be {@code null}
     * @param index the position of the element to be removed
     * @return A new array containing the existing elements except the element
     *         at the specified position.
     * (index < 0 || index >= array.length), or if the array is {@code null}.
     * @since 2.1
     */
    public static char[] remove(char[] array, int index) {

        return (char[]) remove((Object) array, index);
    }


    /**
     * <p>Removes the element at the specified position from the specified array.
     * All subsequent elements are shifted to the left (subtracts one from
     * their indices).</p>
     * <p>This method returns a new array with the same elements of the input
     * array except the element on the specified position. The component
     * type of the returned array is always the same as that of the input
     * array.</p>
     * <p>If the input array is {@code null}, an IndexOutOfBoundsException
     * will be thrown, because in that case no valid index can be specified.</p>
     *
     * @param array the array to remove the element from, may not be {@code null}
     * @param index the position of the element to be removed
     * @return A new array containing the existing elements except the element
     *         at the specified position.
     * (index < 0 || index >= array.length), or if the array is {@code null}.
     * @since 2.1
     */
    private static Object remove(Object array, int index) {

        int length = getLength(array);

        if ((index < 0) || (index >= length)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Length: " + length);
        }

        Object result = Array.newInstance(array.getClass().getComponentType(), length - 1);

        System.arraycopy(array, 0, result, 0, index);

        if (index < length - 1) {
            System.arraycopy(array, index + 1, result, index, length - index - 1);
        }

        return result;
    }


    /**
     * <p>Returns the length of the specified array.
     * This method can deal with <code>Object</code> arrays and with primitive arrays.</p>
     * <p>If the input array is <code>null</code>, <code>0</code> is returned.</p>
     * <pre>
     * ArrayUtils.getLength(null)            = 0
     * ArrayUtils.getLength([])              = 0
     * ArrayUtils.getLength([null])          = 1
     * ArrayUtils.getLength([true, false])   = 2
     * ArrayUtils.getLength([1, 2, 3])       = 3
     * ArrayUtils.getLength(["a", "b", "c"]) = 3
     * </pre>
     *
     * @param array the array to retrieve the length from, may be null
     * @return The length of the array, or <code>0</code> if the array is <code>null</code>
     * @since 2.1
     */
    private static int getLength(Object array) {

        if (array == null) {
            return 0;
        }

        return Array.getLength(array);
    }
}
